package com.jiang.专题.动态规划.Q646;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/30 17:32
 */
class Solution {
    // 动态规划
    // public int findLongestChain(int[][] pairs) {
    //     int len = pairs.length;
    //     Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
    //     int[] dp = new int[len];
    //     Arrays.fill(dp, 1);
    //     for (int i = 0; i < len; i++) {
    //         int j = i - 1;
    //         while (j >= 0) {
    //             if (pairs[i][0] > pairs[j][1]) {
    //                 dp[i] = Math.max(dp[i], dp[j] + 1);
    //             }
    //             j--;
    //         }
    //     }
    //     return dp[len - 1];
    // }

    // 贪心
    public int findLongestChain(int[][] pairs) {
        int len = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int cur = Integer.MIN_VALUE;
        int res = 0;
        for (int[] pair: pairs) {
            if (cur < pair[0]) {
                cur = pair[1];
                res++;
            }
        }
        return res;
    }
}
